Miksi lajitellun taulukon käsittely on nopeampaa kuin lajittelemattoman taulukon käsittely?

Olet haaraennusteiden epäonnistumisen uhri.
Mikä on haaratoiminta?
Harkitse rautatien risteystä:
Kuva Mecanismo Wikimedia Commonsin kautta. Käytetään CC-By-SA 3.0 -lisenssillä.
Oletetaan, että tämä on perustelujen takia jo 1800-luvulla - ennen pitkän matkan tai radioviestintää.
Olet risteyksen operaattori ja kuulet juna saapuvan. Sinulla ei ole aavistustakaan, mihin suuntaan sen pitäisi mennä. Pysäytä juna kysyäksesi kuljettajalta, mihin suuntaan he haluavat. Ja sitten asetat kytkimen asianmukaisesti.
Junat ovat painavia ja niillä on paljon hitautta. Joten heillä on ikuisesti aikaa käynnistää ja hidastaa.
Onko olemassa parempaa tapaa? Luulet mihin suuntaan juna menee!
Jos arvasit oikein, se jatkuu.
Jos arvasit väärin, kapteeni pysähtyy, varmuuskopioi ja huutaa sinua kääntääksesi kytkimen. Sitten se voi aloittaa toisen polun.
Jos arvat oikein joka kerta, junan ei tarvitse koskaan pysähtyä. Jos arvelet väärin liian usein, juna viettää paljon aikaa pysähtymiseen, varmuuskopiointiin ja uudelleenkäynnistykseen.
Harkitse if-lausetta: Prosessoritasolla se on haarakäsky:
Olet prosessori ja näet haaran. Sinulla ei ole aavistustakaan, mihin suuntaan se menee. Mitä sinä teet? Keskeytät suorituksen ja odotat, kunnes edelliset ohjeet on suoritettu. Sitten jatkat oikealla polulla.
Nykyaikaiset prosessorit ovat monimutkaisia ​​ja niillä on pitkät putkistot. Joten heidän kestää ikuisesti "lämmetä" ja "hidastaa".
Onko olemassa parempaa tapaa? Luulet mihin suuntaan haara menee!
Jos arvasit oikein, jatkat suorittamista.
Jos arvasit väärin, sinun on huuhdeltava putki ja rullattava takaisin haaralle. Sitten voit aloittaa toisen polun.
Jos arvat oikein joka kerta, teloituksen ei tarvitse koskaan pysähtyä. Jos arvelet väärin liian usein, vietät paljon aikaa pysähtymiseen, liikkumiseen ja uudelleenkäynnistykseen.
Tämä on haaraennuste. Myönnän, että se ei ole paras analogia, koska juna voisi vain ilmoittaa suunnan lipulla. Mutta tietokoneissa prosessori ei tiedä mihin suuntaan haara menee viimeiseen hetkeen saakka.
Joten miten arvaisit strategisesti minimoidaksesi, kuinka monta kertaa junan on varmuuskopioitava ja mentävä toista polkua pitkin? Katsot menneisyyden historiaa! Jos juna lähtee vasemmalle 99% ajasta, arvat vasemmalle. Jos se vaihtelee, niin voit vuorotella arvauksiasi. Jos se menee yhdellä tavalla joka kolmas kerta, luulet saman ...
Toisin sanoen yrität tunnistaa mallin ja seurata sitä. Tällä tavoin haaran ennustajat toimivat enemmän tai vähemmän.
Useimmissa sovelluksissa on hyvin käyttäytyviä haaroja. Joten nykyaikaiset haaran ennustajat saavuttavat tyypillisesti yli 90% osumaosuudet. Mutta haarojen ennustajat ovat käytännössä hyödyttömiä, kun heillä on odottamattomia haaroja, joilla ei ole tunnistettavissa olevia malleja.
Lisälukemista: "Haaran ennustaja" -artikkeli Wikipediassa.
Kuten ylhäältä vihjain, syyllinen on tämä if-lausunto:
jos (data [c]> = 128)
summa + = data [c];
Huomaa, että data jakautuu tasaisesti 0: n ja 255: n välillä. Kun tiedot lajitellaan, karkeasti iteraatioiden ensimmäinen puolisko ei anna if-käskyä. Sen jälkeen he kaikki syöttävät if-lauseen.
Tämä on hyvin ystävällistä haaran ennustajalle, koska haara kulkee peräkkäin samaan suuntaan monta kertaa. Jopa yksinkertainen kyllästyslaskuri ennustaa haaran oikein, lukuun ottamatta muutamia iteraatioita sen jälkeen, kun se vaihtaa suuntaa.
Nopea visualisointi:
T = haara otettu
N = haaraa ei otettu
data [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
haara = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNNTTTTTTTTT ... TTTTTTTTTT (helppo ennustaa)
Kuitenkin, kun tiedot ovat täysin satunnaisia, haaraennuste tehdään hyödyttömäksi, koska se ei voi ennustaa satunnaisia ​​tietoja. Siten luultavasti noin 50% väärää ennustamista (ei parempaa kuin satunnainen arvaus).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
haara = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (täysin satunnainen - vaikea ennustaa)
Joten mitä voidaan tehdä?
Jos kääntäjä ei pysty optimoimaan haaraa ehdolliseksi siirroksi, voit kokeilla joitain hakkereita, jos olet valmis uhraamaan luettavuuden suorituskyvyn vuoksi.
Korvata:
jos (data [c]> = 128)
summa + = data [c];
kanssa:
int t = (data [c] - 128) >> 31;
summa + = ~ t & data [c];
Tämä eliminoi haaran ja korvaa sen joillakin bittioperaatioilla.
(Huomaa, että tämä hakkerointi ei tarkalleen vastaa alkuperäistä if-käskyä. Mutta tässä tapauksessa se pätee kaikkiin tietojen syöttöarvoihin [].)
Vertailuarvot: Core i7 920, 3,5 GHz
C ++ - Visual Studio 2010 - x64 -julkaisu
// Haara - satunnainen
sekuntia = 11,777
// Haara - lajiteltu
sekuntia = 2.352
// Haaraton - satunnainen
sekuntia = 2,564
// Haaraton - lajiteltu
sekuntia = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Haara - satunnainen
sekuntia = 10.93293813
// Haara - lajiteltu
sekuntia = 5.643797077
// Haaraton -Satunnainen
sekuntia = 3.113581453
// Haaraton - lajiteltu
sekuntia = 3,186068823
Huomautukset:
Haaran kanssa: Lajiteltujen ja lajittelemattomien tietojen välillä on valtava ero.
Hackin kanssa: Lajiteltujen ja lajittelemattomien tietojen välillä ei ole eroa.
C ++ -tapahtumassa hakkerointi on oikeastaan ​​hiukan hitaampaa kuin haaralla, kun tiedot lajitellaan.
Yleinen nyrkkisääntö on välttää tiedoista riippuvainen haarautuminen kriittisissä silmukoissa (kuten tässä esimerkissä).
Päivittää:
GCC 4.6.1, jossa -O3 tai -ftree-vektorize x64: llä, pystyy tuottamaan ehdollisen siirron. Lajiteltujen ja lajittelemattomien tietojen välillä ei siis ole eroa - molemmat ovat nopeita.
(Tai jonkin verran nopeasti: jo lajiteltuun tapaukseen cmov voi olla hitaampi, varsinkin jos GCC asettaa sen kriittiselle polulle vain lisäämisen sijaan, varsinkin Intelissä ennen Broadwellia, jossa cmov: lla on 2 syklin viive: gcc-optimointilippu -O3 tekee koodista hitaampaa kuin -O2)
VC ++ 2010 ei pysty tuottamaan ehdollisia siirtoja tälle haaralle edes / Ox-alla.
Intel C ++ Compiler (ICC) 11 tekee jotain ihmeellistä. Se vaihtaa kaksi silmukkaa ja nostaa siten arvaamattoman haaran ulompaan silmukkaan. Joten se ei ole vain immuuni väärinkäytöksille, se on myös kaksi kertaa nopeampi kuin mitä VC ++ ja GCC voivat tuottaa! Toisin sanoen, ICC käytti testisilmukkaa hyväkseen vertailuarvon ...
Jos annat Intel-kääntäjälle haarattoman koodin, se vain vektorioi sen oikealle ... ja on yhtä nopea kuin haaran kanssa (silmukan vaihdon kanssa).
Tämä osoittaa, että jopa kypsät nykyaikaiset kääntäjät voivat vaihdella rajusti kyvyssä optimoida koodi ...
|
Haaraennuste.
Lajitellun taulukon mukaan ehtodata [c]> = 128 on ensin väärä arvojonolle, sitten siitä tulee totta kaikille myöhemmille arvoille. Se on helppo ennustaa. Lajittelemattomalla taulukolla maksat haarautumiskustannukset.
|
Syy miksi suorituskyky paranee voimakkaasti, kun tiedot lajitellaan, on se, että haaran ennustusrangaistus poistetaan, kuten Mysticialin vastaus kauniisti selittää.
Nyt, jos katsomme koodia
jos (data [c]> = 128)
summa + = data [c];
voimme huomata, että tämän erityisen, jos ... muuten ... haaran merkitys on lisätä jotain, kun ehto täyttyy. Tämän tyyppinen haara voidaan helposti muuttaa ehdolliseksi siirto-käskyksi, joka kootaan ehdolliseksi siirto-ohjeeksi: cmovl, x86-järjestelmässä. Haara ja siten mahdollinen haaran ennustusrangaistus poistetaan.
C: ssä, siis C ++: ssa, lause, joka kääntyy suoraan (ilman optimointia) x86: n ehdolliseen siirto-käskyyn, on kolminkertainen operaattori ...? ...: .... Joten kirjoitamme edellisen lauseen vastaavaksi:
summa + = data [c]> = 128? data [c]: 0;
Samalla kun luettavuus säilyy, voimme tarkistaa nopeuskertoimen.
Intel Core i7-2600K @ 3,4 GHz: n ja Visual Studio 2010 -vapautustilassa vertailuarvo on (muoto kopioitu Mysticialista):
x86
// Haara - satunnainen
sekuntia = 8,885
// Haara - lajiteltu
sekuntia = 1,528
// Haaraton - satunnainen
sekuntia = 3,716
// Haaraton - lajiteltu
sekuntia = 3,71
x64
// Haara - satunnainen
sekuntia = 11.302
// Haara - lajiteltu
sekuntia = 1,830
// Haaraton - satunnainen
sekuntia = 2.736
// Haaraton - lajiteltu
sekuntia = 2.737
Tulos on vankka useissa testeissä. Saamme suuren nopeuden, kun haaran tulos on arvaamaton, mutta kärsimme vähän, kun se on ennustettavissa. Itse asiassa, kun käytetään ehdollista siirtoa, suorituskyky on sama datakuviosta riippumatta.
Tarkastellaan nyt tarkemmin tutkimalla niiden luomaa x86-kokoonpanoa. Yksinkertaisuuden vuoksi käytämme kahta toimintoa max1 ja max2.
max1 käyttää ehdollista haaraa, jos ... muuten ...:
int max1 (int a, int b) {
jos (a> b)
palauta a;
muu
paluu b;
}
max2 käyttää kolmiosaista operaattoria ...? ...: ...:
int max2 (int a, int b) {
palauta a> b? a: b;
}
X86-64-koneella GCC -S luo alla olevan kokoonpanon.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle. L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp. L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
. L4:
movl -12 (% rbp),% eax
lähteä
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
lähteä
ret
max2 käyttää paljon vähemmän koodia johtuen cmovge-ohjeiden käytöstä. Todellinen voitto on kuitenkin se, että max2 ei sisällä haarahyppejä, jmp, jolla olisi merkittävä suoritusrangaistus, jos ennustettu tulos ei ole oikea.
Joten miksi ehdollinen liike toimii paremmin?
Tyypillisessä x86-prosessorissa käskyn suorittaminen on jaettu useisiin vaiheisiin. Karkeasti meillä on erilaisia ​​laitteita käsittelemään eri vaiheita. Joten meidän ei tarvitse odottaa yhden käskyn päättymistä uuden aloittamiseksi. Tätä kutsutaan putkistoksi.
Haaroitustapauksessa seuraava käsky määritetään edellisellä, joten emme voi tehdä putkistoa. Meidän on joko odotettava tai ennustettava.
Ehdollisessa siirtotapauksessasuorituksen ehdollinen siirto-käsky on jaettu useisiin vaiheisiin, mutta aikaisemmat vaiheet, kuten Fetch ja Decode, eivät riipu edellisen käskyn tuloksesta; vain viimeiset vaiheet tarvitsevat tuloksen. Siksi odotamme murto-osaa yhden käskyn suoritusajasta. Siksi ehdollinen siirto-versio on hitaampi kuin haara, kun ennustaminen on helppoa.
Kirja Computer Systems: A Programmer's Perspective, toinen painos, selittää tämän yksityiskohtaisesti. Voit tarkistaa osiosta 3.6.6 ehdolliset siirto-ohjeet, koko luvusta 4 prosessoriarkkitehtuurin ja osiosta 5.11.2 haarakohtaisten ennakointi- ja väärinkäytösrangaistusten erityisen kohtelun.
Joskus jotkut nykyaikaiset kääntäjät voivat optimoida koodin kokoonpanoon paremmalla suorituskyvyllä, joskus jotkut kääntäjät eivät (kyseinen koodi käyttää Visual Studion alkuperäistä kääntäjää). Haaran ja ehdollisen siirron välisen suorituskyvyn eron tunteminen arvaamattomana voi auttaa meitä kirjoittamaan koodia paremmalla suorituskyvyllä, kun skenaario muuttuu niin monimutkaiseksi, että kääntäjä ei voi optimoida niitä automaattisesti.
|
Jos olet kiinnostunut vielä useammasta optimoinnista, jotka tähän koodiin voidaan tehdä, harkitse tätä:
Aloitetaan alkuperäisestä silmukasta:
for (allekirjoittamaton i = 0; i <100000; ++ i)
{
for (allekirjoittamaton j = 0; j  = 128)
summa + = data [j];
}
}
Silmukan vaihdon avulla voimme vaihtaa tämän silmukan turvallisesti:
for (allekirjoittamaton j = 0; j  = 128)
summa + = data [j];
}
}
Sitten voit nähdä, että jos ehdollinen on vakio koko i-silmukan suorituksen ajan, joten voit nostaa if-ulostulon:
for (allekirjoittamaton j = 0; j  = 128)
{
for (allekirjoittamaton i = 0; i <100000; ++ i)
{
summa + = data [j];
}
}
}
Sitten näet, että sisempi silmukka voidaan tiivistää yhdeksi lausekkeeksi, olettaen, että liukulukumalli sallii sen (/ fp: esimerkiksi nopea heitetään)
for (allekirjoittamaton j = 0; j  = 128)
{
summa + = data [j] * 100000;
}
}
Se on 100000 kertaa nopeampi kuin ennen.
|
Jotkut meistä ovat epäilemättä kiinnostuneita tunnistamaan koodin, joka on ongelmallista CPU: n haaraennusteelle. Valgrind-työkalun välimuistissa on haara-ennustussimulaattori, joka on käytössä käyttämällä -branch-sim = yes-lippua. Sen suorittaminen tässä kysymyksessä olevien esimerkkien avulla vähentämällä ulommien silmukoiden lukumäärä 10000: een ja koottu g ++: lla antaa seuraavat tulokset:
Lajiteltu:
== 32551 == Oksat: 656645130 (656609208 cond + 35922 ind)
== 32551 == Väärin ennustettu: 169556 (169955 ehtoa + 461 ind)
== 32551 == Väärin laskettu osuus: 0,0% (0,0% + 1,2%)
Lajittelematta:
== 32555 == Oksat: 655996082 (655960160 cond + 35922 ind)
== 32555 == Väärin ennustettu: 164073152 (164,072,692 cond + 460 ind)
== 32555 == Väärin arvioitu osuus: 25,0% (25,0% + 1,2%)
Kun tarkastellaan cg_annotate -tuotetta rivi riviltä, ​​näemme kyseiselle silmukalle:
Lajiteltu:
Bc Bcm Bi Bim
10 001 4 0 0 (allekirjoittamaton i = 0; i <10000; ++ i)
. . . . {
. . . . // ensisijainen silmukka
327 690 000 10 016 0 0 (allekirjoittamaton c = 0; c  = 128)
0 0 0 0 summa + = data [c];
. . . . }
. . . . }
Lajittelematta:
Bc Bcm Bi Bim
10 001 4 0 0 (allekirjoittamaton i = 0; i <10000; ++ i)
. . . . {
. . . . // ensisijainen silmukka
327,690,000 10,038 0 0 (allekirjoittamaton c = 0; c  = 128)
0 0 0 0 summa + = data [c];
. . . . }
. . . . }
Tämän avulla voit tunnistaa ongelmallisen linjan helposti - lajittelemattomassa versiossa if (data [c]> = 128) -rivi aiheuttaa 164 050 007 väärin ennustettua ehdollista haaraa (Bcm) cachegrindin haara-ennustemallissa, kun taas lajiteltuun versioon se aiheuttaa vain 10 006 .
Vaihtoehtoisesti Linuxissa voit käyttää suorituskyvyn laskureiden alijärjestelmää saman tehtävän suorittamiseen, mutta natiivilla suorituskyvyllä käyttämällä suorittimen laskureita.
perf stat ./sumtest_sorted
Lajiteltu:
Suorituskyvyn laskurit tilastolle './sumtest_sorted':
11808.095776 tehtäväkello # 0.998 suoritinta käytetty
1062 kontekstikytkintä # 0,090 K / s
14 suorittimen siirtoa # 0,001 K / s
337 sivuvirhettä # 0,029 K / s
26 487 882 764 jaksoa # 2,243 GHz
41 025 654 322 ohjeet # 1,55 insns per sykli
6558 871 379 haaraa # 555 455 M / s
567204 haara-ohittaa # 0,01% kaikista haaroista
11,827228330 sekuntia kului
Lajittelematta:
Esitys'./sumtest_unsorted' -laskutilastot:
28877.954344 tehtäväkello # 0.998 suoritinta käytetty
2584 kontekstikytkintä # 0,089 K / s
18 suorittimen siirtoa # 0,001 K / s
335 sivuvirhettä # 0,012 K / s
65,076,127,595 jaksoa # 2,253 GHz
41 032 528 741 ohjeet # 0,63 insns per sykli
6560579013 haaraa # 227,183 M / s
1664394 749 haara-ohittaa # 25,10% kaikista haaroista
28.935500947 sekuntia kului
Se voi myös tehdä lähdekoodimerkinnän purkamalla.
täydellinen ennätys - haara puuttuu ./sumtest_unsorted
täydellinen merkintä -d sumtest_ lajittelematon
Prosenttiosuus Lähdekoodi ja sumtest_unsorted purkaminen
------------------------------------------------
...
: summa + = data [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: Cltq
0,00: 400a28: lisää% rax, -0x30 (% rbp)
...
Katso lisätietoja suorituskyvyn opetusohjelmasta.
|
Luin juuri tämän kysymyksen ja sen vastaukset, ja mielestäni vastaus puuttuu.
Yleinen tapa eliminoida haaraennuste, jonka olen havainnut toimivan erityisen hyvin hallituilla kielillä, on taulukoiden haku haaran käyttämisen sijasta (vaikka en ole testannut sitä tässä tapauksessa).
Tämä lähestymistapa toimii yleensä, jos:
se on pieni pöytä ja todennäköisesti välimuistissa prosessorissa, ja
suoritat asioita melko tiukassa silmukassa ja / tai prosessori voi ladata tiedot esilataukseen.
Tausta ja miksi
Suorittimen näkökulmasta muistisi on hidas. Nopeuseron kompensoimiseksi prosessoriin on rakennettu muutama välimuisti (L1 / L2-välimuisti). Joten kuvittele, että teet hienoja laskelmiasi ja huomaa, että tarvitset muistin. Suoritin saa latausoperaationsa ja lataa muistin välimuistiin - ja käyttää sitten välimuistia loput laskelmat. Koska muisti on suhteellisen hidasta, tämä "lataus" hidastaa ohjelmaa.
Kuten haaran ennakointi, tämä optimoitiin Pentium-prosessoreissa: prosessori ennustaa, että sen on ladattava osa tiedoista, ja yrittää ladata sen välimuistiin ennen kuin operaatio todella osuu välimuistiin. Kuten olemme jo nähneet, haaran ennustus menee joskus pahasti väärin - pahimmassa tapauksessa sinun täytyy palata takaisin ja odottaa todella muistikuormaa, joka kestää ikuisesti (toisin sanoen: epäonnistunut haaraennuste on huono, muisti kuormitus haaraennusteen epäonnistumisen jälkeen on vain kamalaa!).
Meille onneksi, jos muistin käyttömalli on ennustettavissa, prosessori lataa sen nopeaan välimuistiinsa ja kaikki on hyvin.
Ensinnäkin meidän on tiedettävä, mikä on pieni? Vaikka pienempi on yleensä parempi, nyrkkisääntönä on pitää kiinni hakutaulukoista, joiden koko on <= 4096 tavua. Ylärajana: jos hakutaulukko on suurempi kuin 64 kt, se on todennäköisesti syytä harkita uudelleen.
Taulukon rakentaminen
Joten olemme tajunnut, että voimme luoda pienen pöydän. Seuraava tehtävä on saada hakutoiminto paikoilleen. Hakutoiminnot ovat yleensä pieniä toimintoja, jotka käyttävät pari kokonaislukuoperaatiota (ja, tai, xor, siirrä, lisää, poista ja ehkä lisää). Haluat, että hakutoiminto kääntää syötteesi jonkinlaiseksi taulukon `` ainutlaatuiseksi avaimeksi '', joka antaa sitten vastauksen kaikkeen työhön, jonka halusit sen tekevän.
Tässä tapauksessa:> = 128 tarkoittaa, että voimme pitää arvon, <128 tarkoittaa, että pääsemme eroon siitä. Helpoin tapa tehdä se on käyttää JA: ta: jos pidämme sen, me JA se 7FFFFFFF: llä; jos haluamme päästä eroon siitä, me JA se nollalla. Huomaa myös, että 128 on 2: n voima - joten voimme mennä eteenpäin ja tehdä taulukon 32768/128 kokonaisluvusta ja täyttää sen yhdellä nollalla ja paljon 7FFFFFFFF: ää.
Hallinnoidut kielet
Saatat ihmetellä, miksi tämä toimii hyvin hallituilla kielillä. Loppujen lopuksi hallitut kielet tarkistavat matriisien rajat haaralla varmistaaksesi, että et hämmenty ...
No, ei tarkalleen ... :-)
Tämän haaran poistamiseksi hallituille kielille on tehty melko paljon työtä. Esimerkiksi:
for (int i = 0; i  = 128)? c: 0;
}
// Testi
DateTime startTime = System.DateTime.Now;
pitkä summa = 0;
(int i = 0; i <100000; ++ i)
{
// Ensisijainen silmukka
for (int j = 0; j  = 128. Tämä tarkoittaa, että voimme helposti purkaa yhden bitin, joka kertoo meille, haluammeko arvon vai ei: siirtämällä oikealla olevalla 7 bitillä, meille jää 0 tai 1 bitti ja haluamme lisätä arvon vain, kun meillä on 1 bitti. Kutsutaan tätä bittiä "päätösbitiksi".
Käyttämällä päätösbitin 0/1 -arvoa indeksinä matriisina voimme tehdä koodin, joka on yhtä nopea riippumatta siitä, onko data lajiteltu vai ei. Koodimme lisää aina arvoa, mutta kun päätösbitti on 0, lisätään arvo jonnekin, josta emme välitä. Tässä koodi:
// Testi
kellon_aloitus = kello ();
pitkä pitkä a [] = {0, 0};
pitkä pitkä summa;
for (allekirjoittamaton i = 0; i <100000; ++ i)
{
// Ensisijainen silmukka
for (allekirjoittamaton c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (kello () - start) / CLOCKS_PER_SEC;
summa = a [1];
Tämä koodi tuhlaa puolet lisäyksistä, mutta sillä ei koskaan ole haaraennusteiden epäonnistumista. Satunnaisissa tiedoissa se on valtavasti nopeampi kuin todellisen if-lauseen sisältävä versio.
Mutta testissäni nimenomainen hakutaulukko oli hieman tätä nopeampi, luultavasti siksi, että hakutaulukkoon indeksointi oli hieman nopeampi kuin bittisiirto. Tämä osoittaa, kuinka koodini määrittää ja käyttää hakutaulukkoa (koodauksessa mielikuvituksetta kutsutaan lut "LookUp Table": lle). Tässä on C ++ -koodi:
// Ilmoita ja täytä sitten hakutaulukko
int lut [256];
for (allekirjoittamaton c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Käytä hakutaulukkoa sen rakentamisen jälkeen
for (allekirjoittamaton i = 0; i <100000; ++ i)
{
// Ensisijainen silmukka
for (allekirjoittamaton c = 0; c  arvo)
solmu = solmu-> vasen;
muu
solmu = solmu-> pOikea;
tämä kirjasto tekisi jotain:
i = (x  arvo);
solmu = solmu-> linkki [i];
Tässä on linkki tähän koodiin: Punaiset mustat puut, ikuisesti sekava
|
Lajitellussa tapauksessa voit tehdä paremmin kuin luottaa onnistuneeseen haaraennusteeseen tai mihin tahansa haarattomaan vertailutemppuun: poista haara kokonaan.
Taulukko on todellakin osioitu vierekkäiselle vyöhykkeelle, jonka tiedot ovat <128 ja toiset, joiden data> = 128. Joten sinun pitäisi löytää osiopiste dikotomisella haulla (käyttämällä Lg (arraySize) = 15 vertailua), ja suorita sitten suora kerääminen että kohta.
Jotain sellaista (tarkistamaton)
int i = 0, j, k = arraySize;
kun (i > 1;
jos (data [j]> = 128)
k = j;
muu
i = j;
}
summa = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
for (summa = 0; i  = 128)
/ \
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
B) summa + = data [c]; C) silmukalle tai tulostukselle ().
Ilman haaraennustusta tapahtuisi seuraava:
Käskyn B tai käskyn C suorittamiseksi prosessorin on odotettava, kunnes käsky A ei saavu putkilinjan EX-vaiheeseen, koska päätös mennä komentoon B tai ohjeeseen C riippuu käskyn A tuloksesta. näyttää tältä.
kun jos ehto palaa tosi:
Milloin jos ehto palauttaa epätosi:
Käskyn A tuloksen odottamisen seurauksena edellisessä tapauksessa käytettyjen CPU-jaksojen kokonaismäärä (ilman haaraennustusta; sekä tosi että väärä) on 7.
Joten mikä on haaraennuste?
Haaran ennustaja yrittää arvata, mihin suuntaan haara (jos-sitten-muu-rakenne) kulkee, ennen kuin tämä tiedetään varmasti. Se ei odota, että käsky A saavuttaa putkilinjan EX-vaiheen, mutta se arvaa päätöksen ja menee kyseiseen ohjeeseen (B tai C esimerkissämme).
Oikean arvauksen tapauksessa putki näyttää tältä:
Jos myöhemmin havaitaan, että arvaus oli väärä, osittain suoritetut ohjeet hylätään ja putki alkaa uudestaan ​​oikealla haaralla viiveellä.
Aika, joka hukkaan haaran väärän ennusteen sattuessa, on yhtä suuri kuin putkilinjan vaiheiden lukumäärä hakuvaiheesta suoritusvaiheeseen. Nykyaikaisilla mikroprosessoreilla on taipumus olla melko pitkiä putkistoja niin, että väärän ennustamisen viive on 10-20 kellosykliä. Mitä pidempi putki on, sitä enemmän tarvitaan hyvää haaran ennustinta.
OP-koodissa, kun ehdollinen, haaran ennustajalla ei ole ensi ennusteen perustamiseen tarvittavaa tietoa, joten se valitsee ensimmäisen kerran satunnaisesti seuraavan käskyn. Myöhemmin for-silmukassa se voi perustaa ennusteen historiaan.
Nousevassa järjestyksessä olevalle taulukolle on kolme mahdollisuutta:
Kaikki elementit ovat alle 128
Kaikki elementit ovat suurempia kuin 128
Jotkut alkavat uudet elementit ovat alle 128 ja myöhemmin niistä tulee yli 128
Oletetaan, että ennustaja olettaa aina todellisen haaran ensimmäisellä ajona.
Joten ensimmäisessä tapauksessa se on aina tottahaara, koska historiallisesti kaikki sen ennusteet ovat oikeita.
Toisessa tapauksessa se ennustaa aluksi väärin, mutta muutaman iteraation jälkeen se ennustaa oikein.
Kolmannessa tapauksessa se ennustaa aluksi oikein, kunnes elementit ovat alle 128. Tämän jälkeen se epäonnistuu jonkin aikaa ja oikein itse, kun se näkee haaran ennustushäiriön historiassa.
Kaikissa näissä tapauksissa vikojen lukumäärä on liian pieni ja seurauksena on, että vain muutaman kerran sen on hylättävä osittain suoritetut ohjeet ja aloitettava alusta oikealla haaralla, mikä johtaa vähemmän suorittimen jaksoja.
Mutta jos kyseessä on satunnainen lajittelematon taulukko, ennusteen on hylättävä osittain suoritetut käskyt ja aloitettava alusta oikealla haaralla suurimman osan ajasta ja tuloksena enemmän CPU-jaksoja verrattuna lajiteltuun matriisiin.
|
Virallinen vastaus olisi
Intel - haarojen väärinkäytösten kustannusten välttäminen
Intel - haaratoimistojen ja silmukoiden uudelleenjärjestely väärin ennustamisen estämiseksi
Tieteelliset artikkelit - haaraennusteinen tietokonearkkitehtuuri
Kirjat: J.L.Hennessy, D.A. Patterson: Tietokonearkkitehtuuri: kvantitatiivinen lähestymistapa
Artikkelit tieteellisissä julkaisuissa: T.Y. Kyllä, Y.N. Patt teki paljon näistä haaraennusteissa.
Tästä ihanasta kaaviosta näet myös, miksi haaran ennustaja sekoittuu.
Jokainen alkuperäisen koodin elementti on satunnainen arvo
data [c] = std :: rand ()% 256;
joten ennustaja vaihtaa puolta, kun std :: rand () puhaltaa.
Toisaalta, kun ennustaja on lajiteltu, se siirtyy ensin tilaan, jota ei ole otettu voimakkaasti, ja kun arvot muuttuvat suureksi arvoksi, ennustaja muuttuu kolmessa ajassa läpi aina voimakkaasti ottamattomasta vahvasti otettuun.
|
Samalla rivillä (mielestäni tätä ei korostanut mikään vastaus) on hyvä mainita, että joskus (etenkin ohjelmistoissa, joissa suorituskyvyllä on merkitystä - kuten Linux-ytimessä), voit löytää joitain lausekkeita kuten seuraavat:
jos (todennäköisesti (kaikki_is_ok))
{
/* Tee jotain */
}
tai vastaavasti:
jos (epätodennäköistä (hyvin epätodennäköinen_ehto))
{
/* Tee jotain */
}
Sekä todennäköinen () että epätodennäköinen () ovat itse asiassa makroja, jotka määritetään käyttämällä jotain GCC: n __builtin_expect -toimintoa auttaakseen kääntäjää lisäämään ennustuskoodia tilan suosimiseksi ottaen huomioon käyttäjän antamat tiedot. GCC tukee muita sisäänrakennettuja ohjelmia, jotka voivat muuttaa käynnissä olevan ohjelman käyttäytymistä tai antaa matalan tason ohjeita, kuten välimuistin tyhjentäminen, jne. Katso tämä dokumentaatio, joka käy läpi käytettävissä olevat GCC: n sisäiset sisäosat.
Normaalisti tällaiset optimoinnit löytyvät pääasiassa kovan reaaliaikaisista sovelluksista tai sulautetuista järjestelmistä, joissa suoritusajalla on merkitystä ja se on kriittistä. Esimerkiksi, jos olet tarkistamassa virheitä, jotka tapahtuvat vain 1/10000000 kertaa, niin miksi et ilmoittaisi tästä kääntäjälle? Tällä tavoin haaraennuste oletusarvoisesti olettaa, että ehto on väärä.
|
Usein käytetyt Boolen operaatiot C ++: ssa tuottavat monia haaroja käännetyssä ohjelmassa. Jos nämä haarat ovat silmukoiden sisällä ja niitä on vaikea ennustaa, ne voivat hidastaa suoritusta merkittävästi. Boolen muuttujat tallennetaan 8-bittisinä kokonaislukuina, joiden arvo on 0 epätosi ja 1 tosi.
Boolen muuttujat määritetään ylimäärin siinä mielessä, että kaikki operaattorit, joilla on Boolen muuttujia tulona, ​​tarkistavat, onko syötteillä jokin muu arvo kuin 0 tai 1, mutta operaattorit, joilla on Boolean-lähtö, eivät voi tuottaa muuta arvoa kuin 0 tai 1. Tämä tekee operaatioita Boolen muuttujat syötteenä vähemmän tehokkaita kuin tarpeen.
Harkitse esimerkkiä:
bool a, b, c, d;
c = a && b;
d = a || b;
Kääntäjä toteuttaa tämän tyypillisesti seuraavasti:
bool a, b, c, d;
jos (a! = 0) {
jos (b! = 0) {
c = 1;
}
muu {
goto CFALSE;
}
}
muu {
RAHA:
c = 0;
}
jos (a == 0) {
jos (b == 0) {
d = 0;
}
muu {
goto DTRUE;
}
}
muu {
DTRUE:
d = 1;
}
Tämä koodi on kaukana optimaalisesta. Oksat voivat kestää kauan, jos ennakoidaan väärin. Boolen operaatioista voidaan tehdä paljon tehokkaampia, jos varmuudella tiedetään, että operandeilla ei ole muita arvoja kuin 0 ja 1. Syy siihen, miksi kääntäjä ei tee tällaista oletusta, on, että muuttujilla voi olla muita arvoja, jos ne eivät ole alustavia tai tulevat tuntemattomista lähteistä. Yllä oleva koodi voidaan optimoida, jos a ja b on alustettu kelvollisiin arvoihin tai jos ne tulevat operaattoreilta, jotka tuottavat Boolen-lähdön. Optimoitu koodi näyttää tältä:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char: ta käytetään boolin sijasta, jotta bitumisoperaattoreita (& ja |) voidaan käyttää Boolen operaattoreiden (&& ja ||) sijaan. Bittikohtaiset operaattorit ovat yksittäisiä käskyjä, jotka vievät vain yhden kellojakson. OR-operaattori (|) toimii, vaikka a: lla ja b: llä on muut arvot kuin 0 tai 1. AND-operaattori (&) ja EXCLUSIVE OR -operaattori (^) voivat antaa epäjohdonmukaisia ​​tuloksia, jos operandeilla on muita arvoja kuin 0 ja 1.
~ ei voida käyttää EI. Sen sijaan,voit tehdä loogisen EI-muuttujan, jonka tiedetään olevan 0 tai 1 XOR'uttamalla se yhdellä:
bool a, b;
b =! a;
voidaan optimoida:
char a = 0, b;
b = a ^ 1;
a && b: tä ei voida korvata a & b: llä, jos b on lauseke, jota ei tule arvioida, jos a on väärä (&& ei arvioi b: tä & tahtoa). Samoin a || b: tä ei voida korvata a: lla b, jos b on lauseke, jota ei pitäisi arvioida, jos a on totta.
Bittikohtaisten operaattoreiden käyttö on edullisempaa, jos operandit ovat muuttujia, kuin jos operandit ovat vertailuja:
bool a; kaksinkertainen x, y, z;
a = x> y && z <5,0;
on optimaalinen useimmissa tapauksissa (ellet odota, että && -lauseke tuottaa monia haaravirheitä).
|
Se on varmaa!...
Haaraennuste tekee logiikasta hitaamman koodissasi tapahtuvan vaihtamisen takia! Se on kuin menisit suoraan kadulle tai kadulle, jolla on paljon käännöksiä, varmasti suora tehdään nopeammin! ...
Jos taulukko on lajiteltu, ehtosi on väärä ensimmäisessä vaiheessa: data [c]> = 128, ja siitä tulee tosi arvo koko kadun päähän. Näin pääset logiikan loppuun nopeammin. Toisaalta, lajittelemattoman taulukon avulla tarvitset paljon kääntämistä ja käsittelyä, mikä tekee koodistasi hitaamman varmasti ...
Katso alla luotua kuvaa. Mikä katu valmistuu nopeammin?
Joten ohjelmallisesti haaran ennustus saa prosessin hitaammaksi ...
Lopussa on myös hyvä tietää, että meillä on kahdenlaisia ​​haaraennusteita, joista jokainen vaikuttaa koodisi eri tavalla:
1. Staattinen
2. Dynaaminen
Staattinen haaraennuste käytetään mikroprosessorilla ensimmäistä kertaa
ehdollinen haara esiintyy ja dynaaminen haaraennuste on
käytetään ehdollisen haarakoodin onnistuneeseen suorittamiseen.
Voit kirjoittaa koodisi tehokkaasti hyödyntääksesi näitä
säännöt, kun kirjoitat if-else tai vaihda lauseita, tarkista eniten
yleiset tapaukset ensin ja työskentelevät asteittain vähiten yleisiin.
Silmukat eivät välttämättä vaadi erityistä koodin tilausta
staattinen haaraennuste, vain silmukka-iteraattorin ehto
käytetään normaalisti.
|
Tähän kysymykseen on jo vastattu erinomaisesti monta kertaa. Silti haluaisin kiinnittää ryhmän huomion vielä yhteen mielenkiintoiseen analyysiin.
Äskettäin tätä esimerkkiä (muutettu hyvin vähän) käytettiin myös keinona osoittaa, kuinka koodikappale voidaan profiloida itse ohjelman sisällä Windowsissa. Matkan varrella kirjoittaja näyttää myös, kuinka tulosten avulla voidaan selvittää, missä koodi viettää suurimman osan ajastaan ​​sekä lajitellussa että lajittelemattomassa tapauksessa. Lopuksi kappale osoittaa myös, kuinka HAL: n (Hardware Abstraction Layer) vähän tunnettua ominaisuutta voidaan käyttää määrittämään kuinka paljon haaran väärinkäytöksiä tapahtuu lajittelemattomassa tapauksessa.
Linkki on täällä:
Oman profiloinnin esittely
|
Kuten muut ovat jo maininneet, mysteerin takana on haaran ennustaja.
En yritä lisätä jotain, mutta selitän käsitettä toisella tavalla.
Wikissä on tiivis johdanto, joka sisältää tekstiä ja kaavioita.
Pidän alla olevasta selityksestä, joka käyttää kaaviota haaraennustajan kehittämiseen intuitiivisesti.
Tietokonearkkitehtuurissa haaran ennustaja on a
digitaalinen piiri, joka yrittää arvata, mihin suuntaan haara (esim
jos-sitten-muu rakenne) menee ennen kuin tämä tiedetään varmasti.
haaran ennustimen tarkoituksena on parantaa virtausta
ohjeputki. Haaraennustajilla on kriittinen rooli
korkea tehokas suorituskyky monilla nykyaikaisilla putkilinjoilla
mikroprosessoriarkkitehtuurit, kuten x86.
Kaksisuuntainen haaroitus toteutetaan yleensä ehdollisella hyppyllä
ohje. Ehdollista hyppyä voidaan joko "ei tehdä" ja jatkaa
Suoritus suoritetaan koodin ensimmäisellä haaralla, joka seuraa välittömästi
ehdollisen hypyn jälkeen, tai se voidaan "ottaa" ja hypätä kohtaan a
eri paikassa ohjelmamuistissa, jossa koodin toinen haara on
tallennettu. Ei ole varmuutta siitä, onko ehdollinen hyppy
otetaan tai ei oteta ennen kuin ehto on laskettu ja
ehdollinen hyppy on läpäissyt suoritusvaiheen käskyssä
putki (katso kuva 1).
Kuvatun skenaarion perusteella olen kirjoittanut animaatioesittelyn osoittamaan, kuinka käskyt suoritetaan putkessa eri tilanteissa.
Ilman haaran ennustajaa.
Ilman haaraennustetta prosessorin olisi odotettava, kunnes
ehdollinen hyppykäsky on läpäissyt suoritusvaiheen ennen
seuraava käsky voi siirtyä hakuvaiheeseen.
Esimerkki sisältää kolme ohjetta ja ensimmäinen on ehdollinen hyppykäsky. Kaksi jälkimmäistä käskyä voi mennä putkistoon, kunnes ehdollinen hyppykäsky suoritetaan.
Kolmen ohjeen suorittaminen kestää 9 kellosykliä.
Käytä haaraennustajaa ja älä ehdollista hyppyä. Oletetaan, että ennuste ei otaehdollinen hyppy.
Kolmen ohjeen suorittaminen kestää 7 kellosykliä.
Käytä Haaraennustajaa ja hyppää ehdollisesti. Oletetaan, että ennustaminen ei ole ehdollisen hyppyn tekemistä.
Kolmen ohjeen suorittaminen kestää 9 kellosykliä.
Aika, joka tuhlataan haaran väärän ennustamisen yhteydessä, on yhtä suuri kuin
- putkilinjan vaiheiden määrä hakuvaiheesta
suorita vaihe. Nykyaikaisilla mikroprosessoreilla on taipumus olla melko pitkiä
putkilinjoja niin, että virheellisen ennakoinnin viive on välillä 10 ja 20 kelloa
syklit. Tämän seurauksena putkilinjan pidentäminen lisää a: n tarvetta
edistyneempi haaran ennustaja.
Kuten näette, näyttää siltä, ​​että meillä ei ole syytä olla käyttämättä Haaranennustinta.
Se on melko yksinkertainen esittely, joka selventää Branch Predictorin perusosan. Jos nuo gifit ovat ärsyttäviä, poista ne vapaasti vastauksesta ja kävijät voivat myös saada live-demon lähdekoodin BranchPredictorDemosta
|
Haaraennusteiden voitto!
On tärkeää ymmärtää, että haarojen väärinkäyttäminen ei hidasta ohjelmia. Vastaamattoman ennusteen hinta on aivan kuin haaraennustetta ei olisi ollut, ja odotit lausekkeen arviointia päättääksesi mitä koodia suoritetaan (lisäselvitys seuraavassa kappaleessa).
jos (lauseke)
{
// Suorita 1
} muu {
// Suorita 2
}
Aina kun on if-else \ switch-käsky, lauseke on arvioitava suoritettavan lohkon määrittämiseksi. Kääntäjän luomaan kokoonpanokoodiin lisätään ehdolliset haaraohjeet.
Haarakäsky voi saada tietokoneen aloittamaan toisen komentosarjan suorittamisen ja siten poiketa oletusarvoisesta käskyjen suorittamisesta järjestyksessä (ts. Jos lauseke on väärä, ohjelma ohittaa if-lohkon koodin) jostakin ehdosta riippuen. on lausekkeen arviointi meidän tapauksessamme.
Tästä huolimatta kääntäjä yrittää ennustaa lopputuloksen ennen sen tosiasiallista arviointia. Se hakee ohjeet if-lohkosta, ja jos lauseke osoittautuu totta, niin ihana! Saimme aikaa, joka kului sen arviointiin, ja edistyimme koodissa; jos ei, suoritamme väärän koodin, putki huuhdellaan ja oikea lohko suoritetaan.
Visualisointi:
Oletetaan, että sinun on valittava reitti 1 tai reitti 2. Odotat kumppanisi tarkistavan kartan, olet pysähtynyt ## ja odottanut, tai voit vain valita reitin 1 ja jos olet onnekas (reitti 1 on oikea reitti), niin hienoa, että sinun ei tarvinnut odottaa kumppanisi tarkistavan karttaa (säästit aikaa, jonka hän olisi ottanut kartan tarkistamiseen), muuten käännyt vain takaisin.
Putkilinjojen huuhtelu on erittäin nopeaa, mutta nykyään tämä uhkapeli on sen arvoista. Lajiteltujen tietojen tai hitaasti muuttuvien tietojen ennustaminen on aina helpompaa ja parempi kuin nopeiden muutosten ennustaminen.
O Reitti 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Reitti 2 \ --------------------------------
|
ARM: ssä haaraa ei tarvita, koska jokaisella käskyllä ​​on 4-bittinen ehto-kenttä, joka testaa (nollakustannuksilla) minkä tahansa 16 prosessorin tilarekisterissä mahdollisesti esiintyvästä eri tilanteesta ja jos käskyn ehto on väärä, käsky ohitetaan. Tämä eliminoi lyhyiden haarojen tarpeen, eikä tälle algoritmille olisi haaraennusteista osumaa. Siksi tämän algoritmin lajiteltu versio toimisi hitaammin kuin ARM: n lajittelematon versio lajittelun ylimääräisten yleiskustannusten vuoksi.
Tämän algoritmin sisäinen silmukka näyttäisi ARM-kokoonpanokielellä olevan seuraavanlainen:
MOV R0, # 0 // R0 = summa = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = tieto taulukon addr (laita tämä ohje ulomman silmukan ulkopuolelle)
.inner_loop // Sisäisen silmukan haaran tarra
LDRB R3, [R2, R1] // R3 = data [c]
CMP R3, # 128 // vertaa R3: ta 128: een
LISÄÄ R0, R0, R3 // jos R3> = 128, summa + = data [c] - haaraa ei tarvita!
LISÄÄ R1, R1, # 1 // c ++
CMP R1, #arraySize // vertaa c ja arraySize
BLT inner_loop // Haara sisäiseen_loopiin, jos c  ());
for (allekirjoittamaton c = 0; c  = 128
summa = summa + data1 (j);
loppuun
loppuun
loppuun
toc;
ExeTimeWithSorting = toc - tic;
Yllä olevan MATLAB-koodin tulokset ovat seuraavat:
a: Kulunut aika (ilman lajittelua) = 3479,880861 sekuntia.
b: Kulunut aika (lajittelun kanssa) = 2377,873098 sekuntia.
Tulokset C-koodista, kuten @GManNickG: ssä saan:
a: Kulunut aika (ilman lajittelua) = 19,8761 s.
b: Kulunut aika (lajittelun kanssa) = 7,37778 sek.
Tämän perusteella näyttää siltä, ​​että MATLAB on lähes 175 kertaa hitaampi kuin C-toteutus ilman lajittelua ja 350 kertaa hitaampi lajittelun kanssa. Toisin sanoen (haaraennusteen) vaikutus on 1,46x MATLAB-toteutuksessa ja 2,7x C-toteutuksessa.
|
Muiden vastausten oletus, jonka mukaan tiedot on lajiteltava, ei ole oikea.
Seuraava koodi ei lajittele koko taulukkoa, vaan vain 200-elementtisiä segmenttejä ja toimii siten nopeimmin.
Ainoastaan ​​k-elementtiosien lajittelu suorittaa esikäsittelyn lineaarisessa ajassa (O (n)) sen sijaan, että O (n.log (n)) -aika olisi koko taulukon lajittelu.
#include 
#include 
#include 
int main () {
int-data [32768]; const int l = datan koko / datan koko [0];
for (allekirjoittamaton c = 0; c  = 128)
summa + = data [c];
}
}
std :: cout << static_cast  (kello () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << summa << std :: endl;
}
Tämä myös "todistaa", että sillä ei ole mitään tekemistä minkään algoritmisen ongelman, kuten lajittelujärjestyksen kanssa, ja se on todellakin haaraennuste.
|
Bjarne Stroustrupin vastaus tähän kysymykseen:
Se kuulostaa haastattelukysymykseltä. Onko se totta? Miten sinä voisit tietää? On huono idea vastata tehokkuutta koskeviin kysymyksiin tekemättä ensin joitain mittauksia, joten on tärkeää osata mitata.
Joten yritin miljoonan kokonaisluvun vektorilla ja sain:
Lajiteltu jo 32995 millisekuntia
Sekoitettu 125944 millisekuntia
Lajiteltu jo 18610 millisekuntia
Sekoitettu 133304 millisekuntia
Lajiteltu jo 17942 millisekuntia
Sekoitettu 107858 millisekuntia
Juoksin sen muutaman kerran varmistaakseni. Kyllä, ilmiö on todellinen. Avainkoodini oli:
void run (vektori  & v, const-merkkijono ja tunniste)
{
auto t0 = järjestelmän kello :: nyt ();
lajittelu (v.begin (), v.end ());
auto t1 = järjestelmän kello :: nyt ();
cout << etiketti
<< kesto_lähetys  (t1 - t0) .määrä ()
<< "millisekuntia \ n";
}
mitätön tst ()
{
vektori v (1''000'000);
iota (alk. alku (), loppu (), 0);
run (v, "jo lajiteltu");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
juosta (v, "sekoitettu");
}
Ainakin ilmiö on todellinen tämän kääntäjän, vakiokirjaston ja optimoijan asetusten kanssa. Erilaiset toteutukset voivat ja antavat erilaisia ​​vastauksia. Itse asiassa joku teki järjestelmällisemmän tutkimuksen (nopea web-haku löytää sen), ja useimmat toteutukset osoittavat tämän vaikutuksen.
Yksi syy on haaran ennustus: lajittelualgoritmin avainoperaatio on ”if (v [i]  = 128. Tämä tarkoittaa, että voimme helposti purkaa yhden bitin, joka kertoo meille, haluammeko arvon vai ei: siirtämällä oikealla olevalla 7 bitillä, meille jää 0 tai 1 bitti ja haluamme lisätä arvon vain, kun meillä on 1 bitti. Kutsutaan tätä bittiä "päätösbitiksi".
Käyttämällä päätösbitin 0/1 -arvoa indeksinä matriisina voimme tehdä koodin, joka on yhtä nopea riippumatta siitä, onko data lajiteltu vai ei. Koodimme lisää aina arvoa, mutta kun päätösbitti on 0, lisätään arvo jonnekin, josta emme välitä. Tässä koodi:
// Testi
kellon_aloitus = kello ();
pitkä pitkä a [] = {0, 0};
pitkä pitkä summa;
for (allekirjoittamaton i = 0; i <100000; ++ i)
{
// Ensisijainen silmukka
for (allekirjoittamaton c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (kello () - start) / CLOCKS_PER_SEC;
summa = a [1];
Tämä koodi tuhlaa puolet lisäyksistä, mutta sillä ei koskaan ole haaraennusteiden epäonnistumista. Satunnaisissa tiedoissa se on valtavasti nopeampi kuin todellisen if-lauseen sisältävä versio.
Mutta testissäni nimenomainen hakutaulukko oli hieman tätä nopeampi, luultavasti siksi, että hakutaulukkoon indeksointi oli hieman nopeampi kuin bittisiirto. Tämä osoittaa, kuinka koodini määrittää ja käyttää hakutaulukkoa (koodauksessa mielikuvituksetta kutsutaan lut "LookUp Table": lle). Tässä on C ++ -koodi:
// Ilmoita ja täytä sitten hakutaulukko
int lut [256];
for (allekirjoittamaton c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Käytä hakutaulukkoa sen rakentamisen jälkeen
for (allekirjoittamaton i = 0; i <100000; ++ i)
{
// Ensisijainen silmukka
for (allekirjoittamaton c = 0; c  arvo)
solmu = solmu-> vasen;
muu
solmu = solmu-> pOikea;
tämä kirjasto tekisi jotain:
i = (x  arvo);
solmu = solmu-> linkki [i];
Se on mukava ratkaisu ja ehkä se toimii.
|
Erittäin aktiivinen kysymys. Ansaitse 10 mainetta vastaamiseksi tähän kysymykseen. Maineen vaatimus auttaa suojaamaan tätä kysymystä roskapostilta ja vastaamattomuudelta.
Eikö vastausta etsit? Selaa muita kysymyksiä, jotka on merkitty java c ++: n suorituskyvyn optimoinnin haara-ennuste, tai kysy oma kysymyksesi.